package bite;

import java.util.Arrays;
import java.util.Scanner;

/**
 * Creared with IntelliJ IDEA.
 * Description:链接：https://www.nowcoder.com/questionTerminal/a5190a7c3ec045ce9273beebdfe029ee
 * 来源：牛客网
 *
 * 一个袋子里面有n个球，每个球上面都有一个号码(拥有相同号码的球是无区别的)。如果一个袋子是幸运的当且仅当所有球的号码的和大于所有球的号码的积。
 * 例如：如果袋子里面的球的号码是{1, 1, 2, 3}，这个袋子就是幸运的，因为1 + 1 + 2 + 3 > 1 * 1 * 2 * 3
 * 你可以适当从袋子里移除一些球(可以移除0个,但是别移除完)，要使移除后的袋子是幸运的。现在让你编程计算一下你可以获得的多少种不同的幸运的袋子
 * User:yxd
 * Date:2022-04-19
 * Time:16:33
 */
public class Day14_2 {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = input.nextInt();
        }
        Arrays.sort(nums);
        System.out.println(DFS(nums, n, 0, 0, 1));
    }

    public static int DFS(int[] nums, int n, int pos, int sum, int mutil) {
        int count = 0;
        for (int i = pos; i < n; i++) {
            sum += nums[i];
            mutil *= nums[i];
            if(sum > mutil){
                count = count + 1 + DFS(nums,n,i + 1,sum,mutil);//满足条件
            }else if(nums[i] == 1){
                count = count +  DFS(nums,n,i + 1,sum,mutil);//1是一定满足的
            }else{
                break;
            }
            sum -= nums[i];//回溯
            mutil /= nums[i];
            while(i < n - 1 && nums[i] == nums[i + 1]){
                i ++;//所有编号相同的球都是一样的
            }

        }
        return count;
    }
}
